package 蓝桥杯算法;

import 二叉树.TreeNode;

import java.util.*;
import java.util.stream.Collectors;

public class day22 {
    public static void main(String[] args) {
        TreeNode root = new TreeNode(
                new TreeNode(
                        new TreeNode(0),
                        3,
                        new TreeNode(2)
                ),
                1,
                new TreeNode(
                        new TreeNode(0),
                       0 ,
                        new TreeNode(0)
                )
        );
        day22 a=new day22();
        System.out.println(a.isvalid(root));
        System.out.println(a.germinnum(root));
        int[][] arr={{10,16},{2,8},{1,6},{7,12}};
        System.out.println(a.findminshot(arr));
        int[][]arr2={{1,2},{1,2},{1,2}};
        System.out.println(a.finminnus(arr2));
        String s="ababcbacadefegdehijhklij";
        System.out.println(a.partitionLabels(s));
        int[][] arr3={{1,3},{2,6},{8,10},{15,18}};
        System.out.println(a.merge(arr3));



    }
     TreeNode max;
    public boolean isvalid(TreeNode root){
        {
            long prev = Long.MIN_VALUE;//首先定义一个很小的数

            if (root == null) {
                return true;
            }
            if (!isvalid(root.left)) {
                return false;
            }
            if (root.val <= prev) { // 不满足二叉搜索树条件
                return false;
            }
            prev = root.val;
            return isvalid(root.right);
        }
    }
    TreeNode pre;
    int result=Integer.MAX_VALUE;
    public int germinnum(TreeNode root){
        if(root==null){
            return 0;
        }
        traversal(root);
        return result;
    }
    public void traversal(TreeNode root){
        if(root==null){
            return;
        }
        traversal(root.left);
        if(pre!=null){//初次遍历pre没有值
            int num=Math.abs(root.val-pre.val);
            result=Math.min(result,num);
        }
        pre=root;//改变值
        traversal(root.right);
    }

    public int[] findNode(TreeNode root){
       Map<Integer,Integer>map=new HashMap<>();
        List<Integer>list=new ArrayList<>();
        traversal2(root,map);
        int[] res=new int[map.size()];
        List<Map.Entry<Integer,Integer>>mapList=map.entrySet().stream().sorted((c1,c2)->c2.getValue().compareTo
                (c1.getValue())).collect(Collectors.toList());
        list.add(mapList.get(0).getKey());
        for(int i=0;i<mapList.size();i++){
            if(mapList.get(i).getValue()==mapList.get(i-1).getValue()){
                list.add(mapList.get(i).getKey());
            }
            else{
                break;
            }
        }
        return list.stream().mapToInt(Integer::intValue).toArray();

    }
    public void traversal2(TreeNode root,Map<Integer,Integer>map){
        if(root==null){
            return;
        }
        traversal2(root.left,map);
        traversal2(root.right,map);
        map.put(root.val,map.getOrDefault(root.val,0)+1);
    }
    public int findminshot(int[][] points){
        int count=1;
        Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
        for(int i=1;i<points.length;i++){//不存在第零个气球
           if(points[i][0]>points[i-1][1]){//大于开始的节点
               count++;
           }
           else {
               points[i][1]=Math.min(points[i][1],points[i-1][1]);//如果重复判断下一个是否也重复
           }
        }
        return count;
    }
    public int finminnus(int[][] arr){
        Arrays.sort(arr,(a,b)->Integer.compare(a[0],b[0]));
        int count=0;
        for(int i=1;i<arr.length;i++){
            if(arr[i][0]>=arr[i-1][1]){//表示没有重叠
                 continue;
            }
            else{
                arr[i][1]=Math.min(arr[i][1],arr[i-1][1]);//选择右侧值最小的，防止重复
                count++;
            }
        }
        return count;
    }
public List<Integer> partitionLabels(String s){
        List<Integer>list=new ArrayList<>();
        int[] edge=new int[26];
        char[] chars=s.toCharArray();
        for(int i=0;i<chars.length;i++){
            edge[chars[i]-'a']=i;//找到最大限制
        }
        int idx=0;
        int last=-1;
        for(int i=0;i<chars.length;i++){
            //chars[i]-'a'求的是其最大边界
            idx=Math.max(idx,edge[chars[i]-'a']);
            if(idx==i){
              list.add(i-last);//找到该边界
              last=i;
            }
        }
        return list;
}
  public int[][] merge(int[][] intervals){
       List<int[]> res=new ArrayList<>();
        Arrays.sort(intervals,(a,b)->Integer.compare(a[0],b[0]));
        int start=intervals[0][0];
        int end=intervals[0][1];
        for(int i=1;i<intervals.length;i++){
            if(intervals[i][0]>end){
                res.add(new int[]{start,end});//创建新的数组
                start=intervals[i][0];
                end=intervals[i][1];
            }
            else{//存在重叠,更新成更大的结尾
                end=Math.max(end,intervals[i][1]);
            }
        }
        res.add(new int[]{start,end});
        return res.toArray(new int[res.size()][]);
    }
}
